P4451 [国家集训队]整数的lqp拆分

发布于 2020-09-05 | 分类于生成函数 | 4分钟 | 551字数 | 浏览量：

设整数 $n$ 的 $\text{lqp}$ 拆分权值为 $g(n)$ , 那么有：

\begin{cases} g(n)=1 & (n=0) \\ \displaystyle g(n)=\sum_{i=0}^{n-1} fib(i) \times g(n-i) & (n \not=0) \end{cases}

令 $F(x)$ 为斐波拉契数列的 $\text{OGF}$ , $G(x)$ 为 $g$ 的 $\text{OGF}$ 。

卷积就是生成函数的乘法，得到：

G=F*G+1

( 多出来的 $1$ 是让 $g(0)=1$ 的原因 )

又有斐波拉契数列的生成函数：

F(x)=\frac{1}{1-x-x^2}

那么：

G(x)=\frac{1-x-x^2}{1-2x-x^2}

G(x)=1+\frac{x}{1-2x-x^2}

想办法将后面的分数拆开，不妨令 $\frac{x}{1-2x-x^2}=A(\frac{1}{ax-1}-\frac{1}{bx-1})$

然后对比系数解出：

\begin{cases} A=\frac{\sqrt 2}{4} \\ a=1+\sqrt{2} \\ b=1-\sqrt{2} \\ \end{cases}

G(x)=1+\frac{\sqrt 2}{4}(\frac{1}{1-(1+\sqrt{2})x} - \frac{1}{1-(1-\sqrt{2})x})

那么得到：

g(n)=\frac{\sqrt 2}{4} ((1+\sqrt {2})^n - (1-\sqrt {2})^n)

经过枚举你发现 $\sqrt{2}\equiv 59713600 ( \bmod 1e9+7 )$

那么用费马小定理处理指数就可以了。

#include <cstdio>

const int Mod = 1e9 + 7 , Sqrt2 = 59713600;

int Quick_pow( int x , int po ) {
    x = ( x % Mod + Mod ) % Mod;
    int Ans = 1;
    for( ; po ; po >>= 1 , x = 1ll * x * x % Mod )
        if( po & 1 ) Ans = 1ll * Ans * x % Mod;
    return Ans;
}
int Inv( int x ) {
    return Quick_pow( x , Mod - 2 );
}

void Read( int &x ) {
    x = 0; char s = getchar();
    for( ; '0' <= s && s <= '9' ; s = getchar() ) x = ( 10ll * x + s - '0' ) % ( Mod - 1 );
}

int n;
int main( ) {
    Read( n );
    printf("%d\n", ( 1ll * Sqrt2 * Inv( 4 ) % Mod * ( Quick_pow( 1 + Sqrt2 , n ) - Quick_pow( 1 - Sqrt2 , n ) + Mod ) % Mod + Mod ) % Mod );
    return 0;
}

P4451 [国家集训队]整数的lqp拆分

感谢您的支持，我会继续努力的!